/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function (s, wordDict) {
  const dp = new Array(s.length + 1).fill(false)
  const set = new Set(wordDict)
  dp[0] = true
  for (let i = 1; i <= s.length; i++) {
    if (dp[i]) continue
    for (let j = i - 1; j >= 0; j--) {
      if (!dp[j]) continue
      const suffix = s.slice(j, i)
      if (set.has(suffix) && dp[j]) {
        dp[i] = true
        break
      }
    }
  }
  return dp[len]
};
// 还是能用BFS
/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function (s, wordDict) {
  const queue = []
  queue.push(s)
  const visited = {
    [s]: true
  }
  while (queue.length > 0) {
    let len = queue.length
    for (let i = 0; i < len; i++) {
      let tempS = queue.shift()
      if(tempS == '') return true
      for (let j = 0; j < wordDict.length; j++) {
        if (!tempS.startsWith(wordDict[j])) continue
        let str = tempS.substring(wordDict[j].length)
        if (!visited[str]) {
          visited[str] = true
          queue.push(str)
        }
      }
    }
  }
  return false
};
// console.log(wordBreak('leetcode', ['leet', 'code']));
console.log(wordBreak("applepenapple", ['apple', 'pen']));